#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
using namespace std;

//methoid 1 this method will fail if the input is very big
class Solution2 {
    public:
        vector<vector<int> > fourSum(vector<int> &num, int target) {
            set<vector<int> > mySet; 
            vector<vector<int> > rtn;

            if (num.size() < 4) return rtn;

            //sort the input data
            sort(num.begin(), num.end());
            for (int i = 0; i < num.size()-3; i++) {
                if (num[i] > target && num[i] > 0) break;
                for (int j = i+1; j < num.size()-2; j++) {
                    if (num[i] + num[j] > target && num[j] > 0) break;
                    for (int k = j + 1, l = num.size()-1; k < l; ) {
                        if (num[i]+ num[j] + num[k] > target && num[k] > 0) break;
                        //cout << num[i] << " " << num[j] << " " << num[k] << " " << num[l] << endl;
                        vector<int> ans;
                        if (num[i] + num[j] + num[k] + num[l] == target) {
                            ans.push_back(num[i]);
                            ans.push_back(num[j]);
                            ans.push_back(num[k]);
                            ans.push_back(num[l]);
                            mySet.insert(ans);
                            k++;
                            l--;   
                        } else if (num[i] + num[j] + num[k] + num[l] < target) {
                            k++;
                        } else {
                            l--;
                        }
                    }
                }
            }
            for (set<vector<int> >::iterator iter = mySet.begin(); iter != mySet.end(); iter++) {
                rtn.push_back(*iter);
            }
            return rtn;
        }
};

//method 2
class Solution {
    public:
        vector<vector<int> > fourSum(vector<int> &num, int target) {
            map<int, list<pair<int, int> > > myMap;
            set<vector<int> > mySet;
            vector<vector<int> > rtn;

            if (num.size() < 4) return rtn;

            //sort the input data
            sort(num.begin(), num.end());
            for (int i = 0; i < num.size()-1; i++) {
                for (int j = i+1; j < num.size(); j++) {
					int sum = num[i] + num[j];
                    if (myMap.count(target - sum) != 0) {
                        for (list<pair<int, int> >::iterator iter = myMap[target - sum].begin(); iter != myMap[target - sum].end(); iter++) {
                            vector<int> ans1;
                            set<int> ans;
                            ans.insert(i);
                            ans.insert(j);
                            ans.insert(iter->first);
                            ans.insert(iter->second);
                            if (ans.size() == 4) {
                                for (set<int>::iterator  iter = ans.begin(); iter != ans.end(); iter++)
                                    ans1.push_back(num[*iter]);
                                    sort(ans1.begin(), ans1.end());
                                    mySet.insert(ans1);
                                }
                            }
                    }

                    myMap[sum].push_back (make_pair(i, j));
                }
            }
            for (set<vector<int> >::iterator iter = mySet.begin(); iter != mySet.end(); iter++) {
                rtn.push_back(*iter);
            }

            return rtn;
        }
};

//test in online judge and all pass the test.
int main(int argc, char **argv)
{
    Solution mySolution;
    vector<int> input;
//    int test[] = {1,0,-1,0,-2,2};
//    int test[] = {-1, 0, 1, 2};
    int test[] = {1,-2,-5,-4,-3,3,3,5};
    for (int i = 0; i < sizeof(test)/sizeof(int); i++) {
        input.push_back(test[i]);
    }
    vector<vector<int> > result = mySolution.fourSum(input, -11);
    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result[i].size(); j++) {
            cout << result[i][j] << " " ;
        
        }
        cout << endl;
    }

}
